import java.awt.Point;
import java.awt.Polygon;
import java.io.*;
import java.util.LinkedList;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
 
public class SteepestAscentHillClimbing {
	static LinkedList<Point> stack=new LinkedList<Point>();
	static LinkedList<Point> open=new LinkedList<Point>();
	public static String print(Point p){
		return "("+p.x+";"+p.y+")";
	}
	public static boolean isOnSegment(Point2D p1,Point2D p2,Point2D p3){//check p3 on segment p1p2
		Line2D l1=new Line2D.Float(p1,p2);
		Line2D l2=new Line2D.Float(p3,p3);
		if(l1.intersectsLine(l2)) return true;
		return false;
	}
	public static boolean isOnBound(Point2D p,Polygon po){
		if(isOnSegment(new Point(po.xpoints[0],po.ypoints[0]),new Point(po.xpoints[po.npoints-1],po.ypoints[po.npoints-1]),p)) return true;
		for(int i=0;i<po.npoints-1;i++){
			if(isOnSegment(new Point(po.xpoints[i],po.ypoints[i]),new Point(po.xpoints[i+1],po.ypoints[i+1]),p)) return true;
		}
		return false;
	}
	
	public static boolean checkCat(Line2D l1,Line2D l2){
		if(l1.intersectsLine(l2)&&l1.ptLineDist(l2.getP1())!=0.0&&l1.ptLineDist(l2.getP2())!=0.0&&l2.ptLineDist(l1.getP1())!=0.0&&l2.ptLineDist(l1.getP2())!=0.0) return true;
		else return false;
	}
	public static boolean isInPolygon(Point2D center,Polygon po){//check one point is in a Polygon
		Line2D l=new Line2D.Float();
		for(int i=0;i<po.npoints-1;i++){
			l.setLine(po.xpoints[i], po.ypoints[i], po.xpoints[i+1], po.ypoints[i+1]);
			if(l.contains(center)) return true;
		}
		l.setLine(po.xpoints[0], po.ypoints[0], po.xpoints[po.npoints-1], po.ypoints[po.npoints-1]);
		if(l.contains(center)) return true;
		if(po.contains(center)) return true;
		return false;
	}
	public static LinkedList<Point> getPointSeeGoal(Point goal,LinkedList<Point> pointList,Polygon[] po){
		LinkedList<Point> L=new LinkedList<Point>(); 
		for(int i=0;i<pointList.size();i++){
			
			if(!checkCross(pointList.get(i), goal, po)) L.add(pointList.get(i)); 
		}
		return L;
	}
	public static LinkedList<Point> connect2List(LinkedList<Point> l1,LinkedList<Point> l2){
		for(int i=0;i<l2.size();i++){
			l1.add(l2.get(i));
		}
		return l1;
	}
	public static Point bigJump(Point cur,Point goal,LinkedList<Point> pointList,Polygon[] po){
		//LinkedList<Point> seePointList=getSeenPoints(pointList.get(i),po);
		LinkedList<Point> seeGoalList=getPointSeeGoal(goal, pointList, po);
		if(seeGoalList.size()>0) {//have points that see goal 
			LinkedList<Point> nearestPointList=getNearestPoint(seeGoalList,goal);
			if(nearestPointList.size()>1){//hava more than 1 = nearest distant from goal
				LinkedList<Point> curNearestPointList=getNearestPoint(nearestPointList, cur);
				if(curNearestPointList.size()>1) {//only 2 elem in list
					if(isRight(cur,curNearestPointList.get(0),goal)) return curNearestPointList.get(0);
					else return curNearestPointList.get(1);
				}
				else return curNearestPointList.get(0);
			}
			else return nearestPointList.getFirst();
		}
		else{
			LinkedList<Point> choosePointList=new LinkedList<Point>(); 
			LinkedList<Point> seePointList;
			LinkedList<Point> nearestPointList2;
			double min=0;
			for(int i=0;i<pointList.size();i++){
				seePointList=getSeenPoints(pointList.get(i),po);
				nearestPointList2=getNearestPoint(seePointList,goal);
				if(goal.distance(nearestPointList2.get(0))<cur.distance(goal)) {
					if(choosePointList.size()==0){
						choosePointList.add(pointList.get(i));
						min=goal.distance(nearestPointList2.get(0));
					}
					else{
						if(min>goal.distance(nearestPointList2.get(0))){
							choosePointList.clear();
							choosePointList.add(pointList.get(i));
						}
						else if(min==goal.distance(nearestPointList2.get(0))) choosePointList.add(pointList.get(i));
					}
					
				}
			}
			if(choosePointList.size()>1){
				LinkedList<Point> nearGoalPoints= getNearestPoint(choosePointList,goal);
				if(nearGoalPoints.size()>1){
					LinkedList<Point> nearCurrPoints=getNearestPoint(nearGoalPoints,cur);
					if(nearCurrPoints.size()>1){
						if(isRight(cur,nearCurrPoints.get(0),goal)) return nearCurrPoints.get(0);
						else return nearCurrPoints.get(1);
					}
					else return nearCurrPoints.get(0);
				}
				else return nearGoalPoints.get(0);
			}
			else if(choosePointList.size()==1) return choosePointList.get(0);
			else return null;
		}
	}
	public static Point2D intersection2(Line2D l1,Line2D l2) {
	    float d = (float) ((l1.getX1()-l1.getX2())*(l2.getY1()-l2.getY2()) - (l1.getY1()-l1.getY2())*(l2.getX1()-l2.getX2()));
	    if (d == 0) return null;
	    float xi = (float) (((l2.getX1()-l2.getX2())*(l1.getX1()*l1.getY2()-l1.getY1()*l1.getX2())-(l1.getX1()-l1.getX2())*(l2.getX1()*l2.getY2()-l2.getY1()*l2.getX2()))/d);
	    float yi = (float) (((l2.getY1()-l2.getY2())*(l1.getX1()*l1.getY2()-l1.getY1()*l1.getX2())-(l1.getY1()-l1.getY2())*(l2.getX1()*l2.getY2()-l2.getY1()*l2.getX2()))/d);
	    return new Point2D.Float(xi,yi);
	 }
	public static boolean checkCungPhuong(Line2D l1,Line2D l2) {
		 float d = (float) ((l1.getX1()-l1.getX2())*(l2.getY1()-l2.getY2()) - (l1.getY1()-l1.getY2())*(l2.getX1()-l2.getX2()));
		    if (d == 0) return true;
	    else return false;
	 }
	public static boolean checkCross(Point Start,Point End,Polygon[] Pol){
		Line2D l1=new Line2D.Float();
		l1.setLine(Start, End);
		for(int i=0;i<Pol.length;i++){
			LinkedList<Point2D> crossedPoints=new LinkedList<Point2D>();
			for(int j=0;j<Pol[i].npoints-1;j++){
				Line2D l2=new Line2D.Float();
				l2.setLine(Pol[i].xpoints[j],Pol[i].ypoints[j],Pol[i].xpoints[j+1],Pol[i].ypoints[j+1]);
				if(checkCat(l1,l2)) return true;
				if(l1.intersectsLine(l2)) {
					Point2D p=intersection2(l1,l2);
					if(p!=null){
						if(!crossedPoints.contains(p)) crossedPoints.add(p);
					}
					else continue;
				}
				else continue;
			}
			Line2D l2=new Line2D.Float();
			l2.setLine(Pol[i].xpoints[0],Pol[i].ypoints[0],Pol[i].xpoints[Pol[i].npoints-1],Pol[i].ypoints[Pol[i].npoints-1]);
			if(l1.intersectsLine(l2)) {
				Point2D p=intersection2(l1,l2);
				if(p!=null){
					if(!crossedPoints.contains(p)) crossedPoints.add(p);
				}
			}
			//System.out.println(crossedPoints.size());
			if(crossedPoints.size()<2) continue;
			Point2D center=new Point2D.Float(); 
			for(int k=0;k<crossedPoints.size()-1;k++){
				for(int h=k+1;h<crossedPoints.size();h++){
					center.setLocation(1.0*(crossedPoints.get(k).getX()+crossedPoints.get(h).getX())/2,1.0*(crossedPoints.get(k).getY()+crossedPoints.get(h).getY())/2 );
					if(isOnBound(center, Pol[i])) continue;
					
					if(isInPolygon(center,Pol[i])) return true;
				}
			}
			
		}
		return false;
	}
	public static LinkedList<Point> getSeenPoints(Point Current,Polygon[] Pol){//get List of Points that curr can see
		LinkedList<Point> seenPoint=new LinkedList<Point>();
		for(int i=0;i<Pol.length;i++){
			for(int j=0;j<Pol[i].npoints;j++){
				Point tmp=new Point(Pol[i].xpoints[j],Pol[i].ypoints[j]);
				if(!checkCross(Current,tmp,Pol)&&!stack.contains(tmp)) seenPoint.add(tmp);
			}
		}
		return seenPoint;
	}
	public static LinkedList<Point> getNearestPoint(LinkedList<Point> pointList,Point Goal){//get list of nearest point from curr, distant
		LinkedList<Point> nearestPoint=new LinkedList<Point>();
		//System.out.println(pointList);
		double min= Goal.distance(pointList.get(0));
		nearestPoint.add(pointList.get(0));
		for(int i=1;i<pointList.size();i++){
			if(Goal.distance(pointList.get(i))<min){
				nearestPoint.clear();
				min=Goal.distance(pointList.get(i));
				nearestPoint.add(pointList.get(i));
			}
			else if((Goal.distance(pointList.get(i))==min)) nearestPoint.add(pointList.get(i));  
		}
		return nearestPoint;
	}
	public static Point[] getVertex(String line){//get list Vertex polygon
		Point[] Ps;
		String[] tmp=line.substring(2, line.length()-2).split("\\),\\(");
		Ps=new Point[tmp.length];
		for(int i=0;i<tmp.length;i++){
			Ps[i] = new Point(Integer.parseInt(tmp[i].split(",")[0]), Integer.parseInt(tmp[i].split(",")[1]));
		}
		return Ps;
	}
	public static boolean isRight(Point cur,Point p,Point goal){//selection Point that is right from curr
		float xVector1=-(goal.y-cur.y);
		float yVector1=goal.x-cur.x;
		float xVector2=p.x-cur.x;
		float yVector2=p.y-cur.y;
		if(xVector1*xVector2+yVector1*yVector2>0) return true;
		else return false;
	}
	public static Point choosePoint(Point cur,Point goal,Polygon[] po){
		Point Select;
		LinkedList<Point> seePointList=getSeenPoints(cur,po);
		if(seePointList.isEmpty()) return null;
		LinkedList<Point> nearestPointList=getNearestPoint(seePointList,goal);
		Select=nearestPointList.get(0);
		if(cur.distance(goal)<=nearestPointList.get(0).distance(goal)){//there is no point we can get
			Select=bigJump(cur, goal, seePointList, po);
			//System.out.print(bigJump(cur, goal, seePointList, po));
		}
		else{
			if(nearestPointList.size()>1) {// more than 1 point we can get because many points have the same distant from the select point to goal  
				LinkedList<Point> curNearestPointList=getNearestPoint(nearestPointList, cur);
				if(curNearestPointList.size()>1) {//only 2 elem in list
					if(isRight(cur,curNearestPointList.get(0),goal)) Select=curNearestPointList.get(0);
					else Select=curNearestPointList.get(1);
				}
				else Select=curNearestPointList.get(0);
			}
		}
		return Select;
	}
	public static void main(String args[]) throws IOException {
		Point Initial;//Start Point
		Point Goal;//Goal Point
		Point Current;
	    String fileName = args[0];
	    Polygon[] PList;//List of Polygons
	    FileInputStream fstream = new FileInputStream(fileName);
	    DataInputStream in = new DataInputStream(fstream);
	    BufferedReader br = new BufferedReader(new InputStreamReader(in));
	    String strLine;
	    
	    //Read File Line By Line
	    strLine = br.readLine();
	    Initial =new Point(Integer.parseInt(strLine.substring(1,strLine.length()-1 ).split(",")[0]),Integer.parseInt(strLine.substring(1,strLine.length()-1 ).split(",")[1]) );//get Start Point
	    strLine = br.readLine();
	    Goal =new Point(Integer.parseInt(strLine.substring(1,strLine.length()-1 ).split(",")[0]),Integer.parseInt(strLine.substring(1,strLine.length()-1 ).split(",")[1]) );//get Goal Point
	    Current=Initial;
	    strLine = br.readLine();
	    int num;
	    num=Integer.parseInt(strLine);//Num of Polygon
	    PList=new Polygon[num];
	    Point[] t;
	    for(int i=0; i< num;i++){
	    	strLine = br.readLine();
	    	t = getVertex(strLine);
	    	int[] xarr= new int[t.length];
	    	int[] yarr= new int[t.length];
	    	for(int j=0;j<t.length;j++){
	    		xarr[j]=t[j].x;
	    		yarr[j]=t[j].y;
	    	}
	    	PList[i]=new Polygon(xarr, yarr,t.length);
	    }
	    System.out.print(print(Current));
	    stack.add(Current);
    	open.add(Current);
	    while(Current!=Goal){
	    	
	    	if(!checkCross(Current, Goal, PList)) {Current=Goal;System.out.print(","+print(Current));}
	    	else{
	    		Point temp=choosePoint(Current, Goal, PList);
	    		if(temp==null) {
	    			if(Current.equals(Initial)) break;
	    			else{
	    				Point tmpP=Current;
	    				Current=open.get(open.indexOf(Current)-1);
	    				System.out.print(","+print(Current));
		    			open.remove(tmpP);
		    		}
	    		}
	    		else{
		    		Current=temp;
		    		stack.add(Current);
		        	open.add(Current);
		    		System.out.print(","+print(Current));
	    		}
	    	}
	    	
	    }
}
}
